home *** CD-ROM | disk | FTP | other *** search
/ Amiga Game-Power / Amiga Game-Power.iso / pd mix ii / access / hddriver / driver / cache.c < prev    next >
C/C++ Source or Header  |  1994-05-20  |  10KB  |  516 lines
  1.  
  2. /*
  3.  * Copyright 1987 Alan Kent
  4.  *
  5.  * Permission is granted to redistribute this code as long
  6.  * as this message is retained in the code and the code is
  7.  * not sold without written permission from the author.
  8.  *
  9.  * UUCP: {seismo,hplabs,mcvax,ukc,nttlab}!munnari!goanna.oz!ajk
  10.  * ACSnet: ajk@goanna.oz
  11.  * ARPA: munnari!goanna.oz!ajk@SEISMO.ARPA
  12.  */
  13.  
  14.  
  15. #include "hd.h"
  16.  
  17.  
  18. #define CACHE_SIZE        40
  19.  
  20. /* Cache Node types */
  21.  
  22. #define NOT_IN_CACHE    0
  23. #define CN_SPECIAL        1
  24. #define CN_HISTORY        2
  25. #define CN_DIRTY        3
  26.  
  27.  
  28. #define HASH_SIZE        (CACHE_SIZE*3)
  29. #define HASH(block)        (((block)&0x7fff)%HASH_SIZE)
  30.  
  31. static struct cache *    hash_table[ HASH_SIZE ];
  32.  
  33.  
  34. static struct cache {
  35.  
  36.     struct Node node;
  37.     struct cache *collision;
  38.     struct posn posn;
  39.     int            type;
  40.     UBYTE        buf[ HD_SECTOR ];
  41.  
  42. } cache[ CACHE_SIZE ];
  43.  
  44.  
  45. #define DIRTY_LIMIT        10
  46. #define SPECIAL_LIMIT    ( CACHE_SIZE - DIRTY_LIMIT - 7 )
  47. #define MAX_BASES        10
  48.  
  49.  
  50. extern struct cache *    cache_search ();
  51. extern struct Node *    RemHead ();
  52. extern struct Node *    RemTail ();
  53. extern LONG                log_to_phys ();
  54.  
  55.  
  56. static struct List    history;
  57. static struct List    dirty;
  58. static int            num_dirty;
  59. static struct List    special;
  60. static int            special_count;
  61. static int            num_bases = 0;
  62. static LONG            bases[ MAX_BASES ];
  63.  
  64.  
  65. UBYTE *
  66. read_cache ( posn )
  67. struct posn *posn;
  68. {
  69.     register struct cache *c;
  70.     int i;
  71.     struct posn next_posn;
  72.  
  73.  
  74.     /* see if sector is in special cache list */
  75.  
  76.     c = cache_search ( posn );
  77.     if ( c != NULL ) {
  78.  
  79.         switch ( c->type ) {
  80.  
  81.         case CN_SPECIAL :
  82.  
  83.             /* special list still good for a bit longer! */
  84.             
  85.             special_count = 5;
  86.             Remove ( c );
  87.             AddHead ( &history , c );
  88.             c->type = CN_HISTORY;
  89.             return ( c->buf );
  90.  
  91.         case CN_DIRTY :
  92.  
  93.             /* yes, well have to leave it there! */
  94.  
  95.             return ( c->buf );
  96.  
  97.         case CN_HISTORY :
  98.             Remove ( c );
  99.             AddHead ( &history , c );    /* move to head of history */
  100.             c->type = CN_HISTORY;
  101.             return ( c->buf );
  102.         }
  103.     }
  104.  
  105.     /* see if the special_case is really being used for anything */
  106.  
  107.     if ( --special_count <= 0 ) {
  108.  
  109.         /* move everything left in the special cache over to the normal */
  110.         /* cache - it does not seem to be needed anymore */
  111.  
  112.         while ( ( c = (struct cache *)special.lh_Head )->node.ln_Succ != NULL ) {
  113.             Remove ( c );
  114.             AddTail ( &history , c );
  115.             c->type = CN_HISTORY;
  116.         }
  117.     }
  118.  
  119.     /* ok, well we have to actually go and read the sector! */
  120.  
  121.     /* if the special cache list is not empty, just read a sector */
  122.  
  123.     if ( special.lh_Head->ln_Succ != NULL ) {
  124.  
  125.         c = (struct cache *) RemTail ( &history );
  126.         new_posn ( c , posn );
  127.         flush_seek ( &c->posn );
  128.         read_sector ( &c->posn , c->buf );
  129.         analyse ( c , &next_posn );
  130.         AddHead ( &history , c );
  131.         c->type = CN_HISTORY;
  132.         return ( c->buf );
  133.     }
  134.  
  135.     /* ok!! now, the special list is EMPTY! Is the disk access we want */
  136.     /* to do the NEXT of a recently accessed page? */
  137.  
  138.     for ( i = 0, c = (struct cache *) history.lh_Head;
  139.     i < 5  &&  c->node.ln_Succ != NULL;
  140.     i++, c = (struct cache *)c->node.ln_Succ ) {
  141.         if ( is_next ( posn , c ) ) {
  142.  
  143.             /* GOODY! Looks like we have got something to pre-read! */
  144.  
  145.             /* first special entry will be what we asked for */
  146.             next_posn = *posn;
  147.  
  148.             for ( i = 0; i < SPECIAL_LIMIT; i++ ) {
  149.  
  150.                 /* if in any of the caches, dont re-read! */
  151.  
  152.                 if ( cache_search ( &next_posn ) != NULL )
  153.                     break;
  154.  
  155.                 c = (struct cache *) RemTail ( &history );
  156.                 new_posn ( c , &next_posn );
  157.                 flush_seek ( &c->posn );
  158.                 read_sector ( &c->posn , c->buf );
  159.                 analyse ( c , &next_posn );
  160.                 AddTail ( &special , c );
  161.                 c->type = CN_SPECIAL;
  162.  
  163.                 /* end of list will set -ve values */
  164.  
  165.                 if ( next_posn.cylinder < 0 )
  166.                     break;
  167.             }
  168.             c = (struct cache *) special.lh_Head;
  169.             Remove ( c );
  170.             AddHead ( &history , c );
  171.             c->type = CN_HISTORY;
  172.             special_count = 5;
  173.             return ( c->buf );
  174.         }
  175.     }
  176.  
  177.     /* Oh well, its just a boring read then */
  178.  
  179.     c = (struct cache *) RemTail ( &history );
  180.     new_posn ( c , posn );
  181.     flush_seek ( &c->posn );
  182.     read_sector ( &c->posn , c->buf );
  183.     analyse ( c , &next_posn );
  184.     AddHead ( &history , c );
  185.     c->type = CN_HISTORY;
  186.     return ( c->buf );
  187. }
  188.  
  189.  
  190. void
  191. write_cache ( posn , buf )
  192. struct posn *posn;
  193. char *buf;
  194. {
  195.     register struct cache *c , *scan;
  196.  
  197.  
  198.     /* is sector already in a cache? */
  199.  
  200.     c = cache_search ( posn );
  201.     if ( c != NULL ) {
  202.  
  203.         if ( c->type == CN_DIRTY ) {
  204.  
  205.             /* dirty sectors can be left were they are */
  206.  
  207.             copy_sector ( buf , c->buf );
  208.             return;
  209.         }
  210.  
  211.         /* otherwise, fall through - it will have to be put in the */
  212.         /* dirty list */
  213.  
  214.     }
  215.     else {
  216.  
  217.         /* get a cache for the sector. */
  218.  
  219.         c = (struct cache *) history.lh_TailPred;
  220.     }
  221.  
  222.     /* Ok, we have got a sector to put everything in */
  223.  
  224.     Remove ( c );
  225.     new_posn ( c , posn );
  226.     copy_sector ( buf , c->buf );
  227.  
  228.     /* now, we need a sorted insertion to keep dirty list sorted by cyl */
  229.  
  230.     if ( dirty.lh_Head->ln_Succ != NULL ) {
  231.         for ( scan = (struct cache *)dirty.lh_Head;
  232.         scan->node.ln_Succ != NULL;
  233.         scan = (struct cache *) scan->node.ln_Succ ) {
  234.             if ( scan->posn.cylinder > posn->cylinder )
  235.                 break;
  236.         }
  237.         Insert ( &dirty , c , scan->node.ln_Pred );
  238.     }
  239.     else {        /* only node in list */
  240.         AddHead ( &dirty , c );
  241.     }
  242.     c->type = CN_DIRTY;
  243.     num_dirty++;
  244.  
  245.     /* if too many dirty pages, probably should write some out */
  246.  
  247.     if ( num_dirty > DIRTY_LIMIT ) {
  248.  
  249.         /* try and find a close cylinder */
  250.  
  251.         for ( scan = (struct cache *)dirty.lh_Head;
  252.         scan->node.ln_Succ != NULL;
  253.         scan = (struct cache *)scan->node.ln_Succ ) {
  254.             if ( scan->posn.cylinder >= cur_posn.cylinder )
  255.                 break;
  256.         }
  257.  
  258.         /* if at end of list, just use last entry */
  259.  
  260.         if ( scan->node.ln_Succ == NULL )
  261.             scan = (struct cache *) scan->node.ln_Pred;
  262.         write_dirty ( scan );
  263.     }
  264. }
  265.  
  266.  
  267.  
  268. void
  269. flush_all ()
  270. {
  271.     while ( dirty.lh_Head->ln_Succ != NULL )
  272.         write_dirty ( dirty.lh_Head );
  273. }
  274.  
  275.  
  276. write_dirty ( c )
  277. register struct cache *c;
  278. {
  279.     Remove ( c );
  280.     num_dirty--;
  281.     write_sector ( &c->posn , c->buf );
  282.     AddTail ( &history , c );
  283.     c->type = CN_HISTORY;
  284. }
  285.  
  286.  
  287. void
  288. clear_all ()
  289. {
  290.     register int i;
  291.     register struct cache *c;
  292.  
  293.     NewList ( &special );
  294.     NewList ( &dirty );
  295.     NewList ( &history );
  296.     special_count = 0;
  297.     num_dirty = 0;
  298.     for ( i = 0; i < HASH_SIZE; i++ )
  299.         hash_table[i] = NULL;
  300.     for ( i = 0; i < CACHE_SIZE; i++ ) {
  301.         c = &cache[i];
  302.         c->posn.cylinder = -3;
  303.         c->posn.sector = 0;
  304.         c->posn.surface = 0;
  305.         c->posn.block = -3 * first.sectors * first.heads;
  306.         AddTail ( &history , c );
  307.         c->type = CN_HISTORY;
  308.         c->collision = hash_table[ HASH(c->posn.block) ];
  309.         hash_table[ HASH(c->posn.block) ] = c;
  310.     }
  311. }
  312.  
  313.  
  314. int
  315. init_cache ()
  316. {
  317.     register int i;
  318.  
  319.     clear_all ();
  320.     return ( 0 );
  321. }
  322.  
  323.  
  324. void
  325. free_cache ()
  326. {
  327.     register int i;
  328.  
  329.     flush_all ();
  330. }
  331.  
  332.  
  333. struct cache *
  334. cache_search ( posn )
  335. register struct posn *posn;
  336. {
  337.     register struct cache *c;
  338.  
  339.     c = hash_table[ HASH(posn->block) ];
  340.     while ( c != NULL ) {
  341.         if ( posn->block == c->posn.block )
  342.             return ( c );
  343.         c = c->collision;
  344.     }
  345.     return ( NULL );
  346. }
  347.  
  348.  
  349. new_posn ( c , posn )
  350. register struct cache *c;
  351. struct posn *posn;
  352. {
  353.     register struct cache **old;
  354.     register struct cache **h;
  355.  
  356.     /* first, remove from existing hash table position */
  357.  
  358.     old = &hash_table[ HASH(c->posn.block) ];
  359.     while ( *old != NULL ) {
  360.         if ( *old == c ) {                /* found pointer to c */
  361.             *old = (*old)->collision;    /* unlink node */
  362.             break;
  363.         }
  364.         old = &(*old)->collision;
  365.     }
  366.  
  367.     /* now update the position */
  368.  
  369.     c->posn = *posn;
  370.  
  371.     /* now insert into hash table at new position */
  372.  
  373.     h = &hash_table[ HASH(c->posn.block) ];
  374.     c->collision = *h;
  375.     *h = c;
  376. }
  377.  
  378.  
  379.  
  380. flush_seek ( posn ) /* write out all dirty tracks on way to posn */
  381. struct posn *posn;
  382. {
  383.     register struct cache *c;
  384.  
  385.     if ( posn->cylinder > cur_posn.cylinder ) {
  386.         for ( c = (struct cache *)dirty.lh_Head;
  387.         c->node.ln_Succ != NULL;
  388.         c = (struct cache *)c->node.ln_Succ ) {
  389.             if ( c->posn.cylinder >= cur_posn.cylinder
  390.             &&  c->posn.cylinder <= posn->cylinder ) {
  391.                 c = (struct cache *)c->node.ln_Pred;
  392.                 write_dirty ( c->node.ln_Succ );
  393.             }
  394.         }
  395.     }
  396.     else {
  397.         for ( c = (struct cache *)dirty.lh_TailPred;
  398.         c->node.ln_Pred != NULL;
  399.         c = (struct cache *)c->node.ln_Pred ) {
  400.             if ( c->posn.cylinder <= cur_posn.cylinder + 1
  401.             &&  c->posn.cylinder >= posn->cylinder ) {
  402.                 c = (struct cache *)c->node.ln_Succ;
  403.                 write_dirty ( c->node.ln_Pred );
  404.             }
  405.         }
  406.     }
  407. }
  408.  
  409.  
  410. /* have a look, check block # to see if any new partitions */
  411. analyse ( c , next_posn )
  412. register struct cache *c;
  413. register struct posn *next_posn;
  414. {
  415.     LONG logical_block , base;
  416.     LONG type , subtype;
  417.     ULONG *buf;
  418.  
  419.  
  420.     buf = (ULONG*) c->buf;
  421.     type = buf[0];
  422.     subtype = buf[127];
  423.  
  424.     if ( type == 2  &&  subtype == 2        /* File Header */
  425.     ||   type == 2  &&  subtype == -3 ) {    /* User Directory */
  426.  
  427.         /* these blocks point to themselves, so we can use block # */
  428.         /* to work out where partitions start */
  429.  
  430.         base = c->posn.block - buf[1];
  431.  
  432.         /* see if we know about this base yet, if not add it */
  433.  
  434.         new_base ( base );
  435.     }
  436.  
  437.     /* ok, now look for a next pointer */
  438.  
  439.     get_next ( c , next_posn );
  440. }
  441.  
  442.  
  443. get_next ( c , next_posn )
  444. register struct cache *c;
  445. register struct posn *next_posn;
  446. {
  447.     LONG type , subtype , next , block;
  448.     ULONG *buf;
  449.  
  450.     buf = (ULONG *) c->buf;
  451.     type = buf[0];
  452.     subtype = buf[127];
  453.     next = buf[4];
  454.  
  455.     next_posn->block = -1;
  456.     next_posn->sector = -1;
  457.     next_posn->surface = -1;
  458.     next_posn->cylinder = -1;
  459.  
  460.     if ( type == 2  &&  subtype == -3        /* file header */
  461.     ||   type == 16 &&  subtype == -3        /* file extension */
  462.     ||   type == 8 ) {                        /* data block */
  463.         block = log_to_phys ( c->posn.block , next );
  464.         if ( block >= 0
  465.         &&  block < first.sectors * first.heads * first.cylinders ) {
  466.             next_posn->block = block;
  467.             next_posn->sector = block % first.sectors;
  468.             next_posn->surface = ( block / first.sectors ) % first.heads;
  469.             next_posn->cylinder = block / ( first.sectors * first.heads );
  470.         }
  471.     }
  472. }
  473.  
  474.  
  475. LONG
  476. log_to_phys ( real , logical )
  477. LONG real , logical;
  478. {
  479.     register int i;
  480.  
  481.     for ( i = num_bases - 1; i >= 0; i-- )
  482.         if ( real >= bases[i] )
  483.             return ( logical + bases[i] );
  484.     return ( -1 );
  485. }
  486.  
  487.  
  488. new_base ( base )
  489. LONG base;
  490. {
  491.     register int i , j;
  492.  
  493.     for ( i = num_bases - 1; i >= 0; i-- ) {
  494.         if ( bases[i] == base )
  495.             return;
  496.         if ( bases[i] < base )
  497.             break;
  498.     }
  499.     i++;
  500.     for ( j = num_bases; j > i; j-- )
  501.         bases[j] = bases[j-1];
  502.     bases[i] = base;
  503.     num_bases++;
  504. }
  505.  
  506.  
  507. is_next ( posn , c )
  508. struct posn *posn;
  509. struct cache *c;
  510. {
  511.     struct posn next_posn;
  512.  
  513.     get_next ( c , &next_posn );
  514.     return ( posn->block == next_posn.block );
  515. }
  516.